/**** 翻转链表 ****/
#include <iostream>
 
using namespace std;


struct ListNode 
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) 
    {
        if(head == nullptr)
        {
            return nullptr;
        }
        ListNode * prev = nullptr;
        ListNode * current = head;

        while(current != nullptr)
        {
            ListNode* nextNode = current->next; // 提前保存下一个节点,这里一定要保存下一个节点
            current->next = prev;               // 当前节点指向前一个节点
            prev = current;                     // prev移动到当前节点
            current = nextNode;                 // current移动到下一个节点
        }
        return prev;                    // 返回的prev翻转为头指针了
        
        // write code here
    }
};

int main()
{
    ListNode * node1 = new ListNode(1);
    ListNode * node2 = new ListNode(2);
    ListNode * node3 = new ListNode(3);

    node1->next = node2;
    node2->next = node3;

    ListNode * travelPoint = node1;
    while(travelPoint != nullptr)
    {
        cout << travelPoint->val << " " ;
        travelPoint = travelPoint->next;
    }
    cout << endl;

    Solution solu;
    
    ListNode * ReverseHead = solu.ReverseList(node1);

    travelPoint = ReverseHead;
    while(travelPoint != nullptr)
    {
        cout << travelPoint->val << " " ;
        travelPoint = travelPoint->next;
    }
    cout << endl;

    return 0;
}